import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-23
 * Time: 10:21
 */
public class Solution2 {
    public boolean isPail (ListNode head) {
        //方法二：栈逆序
        /*时间复杂度是O(n)，遍历链表入栈是O(n),后续再遍历栈和链表是O(n)
        * 空间复杂度是O(n),记录链表元素的辅助栈*/
        Stack<Integer> stack=new Stack<>();
        ListNode cur=head;
        while (cur!=null){
            //将链表顺序入栈
            stack.push(cur.val);
            cur=cur.next;
        }
        cur=head;
        while (!stack.isEmpty()){
            if(cur.val!=stack.pop()){
                return false;
            }
            cur=cur.next;
        }
        return true;
    }
}
